﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Inspired.Euler
{
    /// <summary>
    /// The following iterative sequence is defined for the set of positive integers:
    /// 
    /// n = n/2 (n is even)
    /// n = 3n + 1 (n is odd)
    /// 
    /// Using the rule above and starting with 13, we generate the following sequence:
    /// 
    /// 13  40  20  10  5  16  8  4  2  1
    /// It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. 
    /// Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
    /// 
    /// Which starting number, under one million, produces the longest chain?
    /// 
    /// NOTE: Once the chain starts the terms are allowed to go above one million.
    /// </summary>
    public static class Problem014
    {
        /// <summary>
        /// Find the longest sequence using a starting number under one million.
        /// </summary>
        [EulerProblem(14, Title = "Find the longest sequence using a starting number under one million.")]
        public static long Solve()
        {
            return(
                Enumerable.Range(1, 999999)
                    .Select(number => new { Seed = number, Terms = ((long)number).GetSequence().Count })
                    .OrderByDescending(pair => pair.Terms)
                    .First().Seed
                    );
        }

        static List<long> GetSequence(this long seed)
        {
            List<long> sequence = new List<long>() { seed };
            while (seed > 1)
            {
                seed = seed % 2 == 0 ? seed / 2 : (3 * seed) + 1;
                sequence.Add(seed);
            }
            return sequence;
        }
    }
}
